/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-17
 * Time:23:23
 */

/**
 * JZ7重建二叉树
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class reConstructBinaryTree {
    //    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
//        TreeNode root = new TreeNode(pre[0]);
//        int rootIndex = 0;
//        for (int i = 0; i < vin.length; i++) {
//            if (vin[i] == pre[0]) {
//                rootIndex = i;//找到根节点子在中序遍历中的下标
//            }
//        }
////        buildLeft(root,rootIndex,pre,vin);//建造左子树
////        buildRight(root,rootIndex,pre,vin);//建造右子树
//
//
//        return root;
//    }
//
//    //    private void buildRight(TreeNode root, int rootIndex,int [] pre,int [] vin) {
////        int indexR = 1;
////        root.left = new TreeNode(pre[indexR]);
////    }
////
////    private void buildLeft(TreeNode root, int rootIndex,int [] pre,int [] vin) {
////
////    }
//    private TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
//        if (preStart > preEnd || inStart > inEnd) {
//            return null;
//        }
//        int rootVal = preOrder[preStart];
//        int rootIndex = 0;
//        for (int i = inStart; i <= inEnd; i++) {
//            if (inOrder[i] == rootVal) {
//                rootIndex = i;
//                break;
//            }
//        }
//        int leftSize = rootIndex - inStart;
//        TreeNode root = new TreeNode(rootVal);
//        root.left = buildTree(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, rootIndex - 1);
//        root.right = buildTree(preOrder, preStart + leftSize + 1, preEnd, inOrder, rootIndex + 1, inEnd);
//        return root;
//    }
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        return buildTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }

    private TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int inIndex = findIndex(in, inStart, inEnd, pre[preStart]);
        int leftLength = inIndex - inStart;
        root.left = buildTree(pre, in, preStart + 1, preStart + leftLength, inStart, inIndex - 1);
        root.right = buildTree(pre, in, preStart + leftLength + 1, preEnd, inIndex + 1, inEnd);
        return root;
    }

    private int findIndex(int[] array, int start, int end, int value) {
        for (int i = start; i <= end; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }
}
